//最小栈
/*设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
  -231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次
*/
class MinStack {
public:
    MinStack() {}

    void push(int val) {
        n1.push(val);
        if (n2.empty())
            n2.push(val);
        else if (n2.top() >= val)
            n2.push(val);
    }

    void pop() {
        if (n1.top() == n2.top())
            n2.pop();
        n1.pop();
    }

    int top() { return n1.top(); }

    int getMin() { return n2.top(); }

private:
    stack<int> n1;
    stack<int> n2;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */



 //栈的压入、弹出序列
 /*输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
*/
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型vector
     * @param popV int整型vector
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        stack<int>Stack;
        int pop_index = 0;
        for (auto& val : pushV) {
            Stack.push(val);
            while (pop_index < popV.size() && Stack.size() &&
                    Stack.top() == popV[pop_index]) {
                Stack.pop();
                pop_index++;
            }
        }
        return Stack.empty();
    }
};